|
A Turing machine is an abstract "machine"〔Minsky 1967:107 "In his 1936 paper, A. M. Turing defined the class of abstract machines that now bear his name. A Turing machine is a finite-state machine associated with a special kind of environment -- its tape -- in which it can store (and later recover) sequences of symbols", also Stone 1972:8 where the word "machine" is in quotation marks.〕 that manipulates symbols on a strip of tape according to a table of rules; to be more exact, it is a mathematical model that defines such a device.〔Stone 1972:8 states "This "machine" is an abstract mathematical model", also cf Sipser 2006:137ff that describes the "Turing machine model". Rogers 1987 (1967):13 refers to "Turing's characterization", Boolos Burgess and Jeffrey 2002:25 refers to a "specific kind of idealized machine".〕 Despite the model's simplicity, given any computer algorithm, a Turing machine can be constructed that is capable of simulating that algorithm's logic.〔Sipser 2006:137 "A Turing machine can do everything that a real computer can do".〕 The machine operates on an infinite〔cf Sipser 2002:137. Also Rogers 1987 (1967):13 describes "a paper tape of infinite length in both directions". Minsky 1967:118 states "The tape is regarded as infinite in both directions". Boolos Burgess and Jeffrey 2002:25 include the possibility of "there is someone stationed at each end to add extra blank squares as needed".〕 memory tape divided into ''cells''.〔cf Rogers 1987 (1967):13. Other authors use the word "square" e.g. Boolos Burgess Jeffrey 2002:35, Minsky 1967:117, Penrose 1989:37.〕 The machine positions its ''head'' over a cell and "reads" (scans〔The word used by e.g. Davis 2000:151〕) the symbol there. Then per the symbol and its present place in a ''finite table''〔This table represents an algorithm or "effective computational procedure" which is necessarily finite; see Penrose 1989:30ff, Stone 1972:3ff.〕 of user-specified instructions the machine (i) writes a symbol (e.g. a digit or a letter from a finite alphabet) in the cell (some models allowing symbol erasure〔Boolos Burgess and Jeffrey 2002:25〕 and/or no writing), then (ii) either moves the tape one cell left or right (some models allow no motion, some models move the head),〔Boolos Burgess Jeffry 2002:25 illustrate the machine as moving along the tape. Penrose 1989:36-37 describes himself as "uncomfortable" with an infinite tape observing that it "might be hard to shift!"; he "prefer() to think of the tape as representing some external environment through which our finite device can move" and after observing that the " 'movement' is a convenient way of picturing things" and then suggests that "the device receives all its input from this environment.〕 then (iii) (as determined by the observed symbol and the machine's place in the table) either proceeds to a subsequent instruction or halts〔"Also by convention one of the states is distinguished as the stopping state and is given the name HALT" (Stone 1972:9). Turing's original description did not include a HALT instruction but he did allow for a "circular" condition, a "configuration from which there is no possible move" (see Turing 1936 in ''The Undecidable'' 1967:119); this notion was added in the 1950s; see more at Halting problem.〕 the computation. The Turing machine was invented in 1936 by Alan Turing,〔The idea came to him in mid-1935 (perhaps, see more in the History section) after a question posed by M. H. A. Newman in his lectures: "Was there a definite method, or as Newman put it, a ''mechanical process'' which could be applied to a mathematical statement, and which would come up with the answer as to whether it was provable" (Hodges 1983:93). Turing submitted his paper on 31 May 1936 to the London Mathematical Society for its ''Proceedings'' (cf Hodges 1983:112), but it was ''published'' in early 1937 and offprints were available in February 1937 (cf Hodges 1983:129).〕 who called it an ''a-machine'' (automatic machine).〔See footnote in Davis 2000:151.〕 With this model Turing was able to answer two questions in the negative: (1) Does a machine exist that can determine whether any arbitrary machine on its tape is "circular" (e.g. freezes, or fails to continue its computational task); similarly, (2) does a machine exist that can determine whether any arbitrary machine on its tape ever prints a given symbol.〔Turing 1936 in ''The Undecidable'' 1965:132-134; Turing's definition of "circular" is found on page 119.〕 Thus by providing a mathematical description of a very simple device capable of arbitrary computations, he was able to prove properties of computation in general - and in particular, the uncomputability of the Hilbert Entscheidungsproblem ("decision problem").〔Turing 1936 in ''The Undecidable'' 1965:145〕 Thus, Turing machines prove fundamental limitations on the power of mechanical computation.〔Sipser 2006:137 observes that "A Turing machine can do everything that a real computer can do. Nevertheless, even a Turing machine cannot solve certain problems. In a very real sense, these problems are beyond the theoretical limits of computation."〕 While they can express arbitrary computations, their minimalistic design makes them unsuitable for computation in practice: actual computers are based on different designs that, unlike Turing machines, use random access memory. Turing completeness is the ability for a system of instructions to simulate a Turing machine. A programming language that is Turing complete is theoretically capable of expressing all tasks accomplishable by computers; nearly all programming languages are Turing complete. ==Overview== A Turing machine is a general example of a CPU that controls all data manipulation done by a computer, with the canonical machine using sequential memory to store data. More specifically, it is a machine (automaton) capable of enumerating some arbitrary subset of valid strings of an alphabet; these strings are part of a recursively enumerable set. Assuming a black box, the Turing machine cannot know whether it will eventually enumerate any one specific string of the subset with a given program. This is due to the fact that the halting problem is unsolvable, which has major implications for the theoretical limits of computing. The Turing machine is capable of processing an unrestricted grammar, which further implies that it is capable of robustly evaluating first-order logic in an infinite number of ways. This is famously demonstrated through lambda calculus. A Turing machine that is able to simulate any other Turing machine is called a universal Turing machine (UTM, or simply a universal machine). A more mathematically oriented definition with a similar "universal" nature was introduced by Alonzo Church, whose work on lambda calculus intertwined with Turing's in a formal theory of computation known as the Church–Turing thesis. The thesis states that Turing machines indeed capture the informal notion of effective methods in logic and mathematics, and provide a precise definition of an algorithm or "mechanical procedure". Studying their abstract properties yields many insights into computer science and complexity theory. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Turing machine」の詳細全文を読む スポンサード リンク
|